package com.kabuda.zhugehot200;

/**
 * @author kabuda
 * @date 2025-03-15 20:32
 * @description
 */
public class t509_斐波那契数列 {
    public static void main(String[] args) {
        System.out.println(recursion(10));
        System.out.println(recursion2(10));
        System.out.println(iterate(10));
    }

    /**
     * 暴力递归
     *
     * @param n
     * @return
     */
    public static int recursion(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        return recursion(n - 1) + recursion(n - 2);
    }


    /**
     * 去重递归
     *
     * @param n
     * @return
     */
    public static int recursion2(int n) {
        int[] ints = new int[n + 1];
        return deWeightRecursion(ints, n - 1) + deWeightRecursion(ints, n - 2);

    }

    public static int deWeightRecursion(int[] arr, int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (arr[n] != 0) {
            return arr[n];
        }

        arr[n] = deWeightRecursion(arr, n - 1) + deWeightRecursion(arr, n - 2);
        return arr[n];
    }

    /**
     * 双指针迭代
     * @param n
     * @return
     */
    public static int iterate(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int low=0;
        int high=1;
        int sum=0;
        for (int i = 2; i <= n; i++) {
            sum=low+high;
            low=high;
            high=sum;
        }
        return sum;
    }


}
